package com.zlk.algorithm.algorithm.sort.quick;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName QuickSort
 * @description: 快速排序
 * quick1 与quick2 的时间复杂度都是 n的平方 因为最差时间复杂度为n方 （退化成冒泡排序之类的）
 * quick3 随即 所有期望和导致时间复杂度  nlogn
 * https://www.nowcoder.com/practice/3385982ae71d4a1ca8bf3d03614c0325
 * @author: slfang
 * @create: 2024-01-22 09:46
 * @Version 1.0
 **/
public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点
            int partitionIndex = partition(arr, low, high);

            // 递归排序左子数组
            quickSort(arr, low, partitionIndex - 1);

            // 递归排序右子数组
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最右边的元素作为基准值(pivot)
        int pivot = arr[high];

        // 指向小于基准值的元素的边界
        int i = low - 1;

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准值
            if (arr[j] <= pivot) {
                i++;
                // 交换arr[i]和arr[j]
                SortUtils.swap(arr, i, j);
            }
        }

        // 将基准值放到正确的位置
        SortUtils.swap(arr, i + 1, high);

        return i + 1;
    }

    @Test
    public void test(){
        int testTimes = 10000;
        int randomLength = 20;
        int randomVal = 100;

        for (int i = 0; i < testTimes; i++) {
            int[] randomArr1 = SortUtils.getRandomArr(randomVal, randomLength);
            int[] copy = SortUtils.copyArray(randomArr1);
            SortUtils.comparator(copy);
            quickSort(randomArr1);
            //heapSort(randomArr1);
            if(!SortUtils.isEqual(copy,randomArr1)){
                System.out.println("第"+(i+1)+"测试失败"+ Arrays.toString(copy));
                System.out.println("第"+(i+1)+"测试失败"+ Arrays.toString(randomArr1));
            }
        }
        System.out.println("success !!!");
    }

}
